package const_prop;

/********************************
 * Authors: Gustavo Solaira and Rafael Dominiquini
 * MC011 - Constant Propagation
 ********************************/

import java.io.PrintStream;
import java.util.HashSet;
import java.util.Hashtable;

import temp.Temp;
import util.List;
import flow_graph.AssemFlowGraph;
import graph.Node;
import assem.Instr;

public class ReachingDefs 
{	
	private AssemFlowGraph graph;
    
    // estruturas usadas para computar a DFA
    private Hashtable<Node, HashSet<Instr>> in;
    private Hashtable<Node, HashSet<Instr>> out;
    private Hashtable<Node, HashSet<Instr>> gen;
    private Hashtable<Node, HashSet<Instr>> kill;
    
    private Hashtable<Temp, HashSet<Instr>> defs;
    
    public ReachingDefs(AssemFlowGraph g)
    {
        super();
    
        graph = g;
        
        if (graph == null)
        {
        	return;
        }
                    
        computeGenKill();
        computeDFA();
        
//        dump(System.out);
    }

    public void dump(PrintStream outStream)
    {
        int c=0;
        for(List<Node> aux = graph.nodes(); aux != null; aux = aux.tail, c++)
        {
            HashSet<Instr> i = in.get(aux.head);
            HashSet<Instr> o = out.get(aux.head);
            HashSet<Instr> g = gen.get(aux.head);
            HashSet<Instr> k = kill.get(aux.head);
            
            outStream.println(c+": gen:"+g+" kill:"+k+" in:"+i+" out:"+o);
        }
    }
    
    private void computeGenKill()
    {
        kill = new Hashtable<Node, HashSet<Instr>>();
        gen  = new Hashtable<Node, HashSet<Instr>>();
        defs = new Hashtable<Temp, HashSet<Instr>>();
        
        Instr inst;
        
        // gen
        // calculate gen for all nodes that define something
        for(List<Node> nodes = graph.nodes(); nodes != null; nodes = nodes.tail)
        {
            HashSet<Instr> g = new HashSet<Instr>();
            inst = graph.instr(nodes.head);
            
            // verifica se ele define alguma coisa
            if (inst.def() != null && inst.def().size() > 0)
            {
	            g.add(inst);
	            
	            for ( List<Temp> aux = graph.def(nodes.head); aux != null; aux = aux.tail )
	            {
	            	// adiciona ao defs to temporario
	            	if (defs.containsKey(aux.head))
	            	{
	            		defs.get(aux.head).add(inst);
	            	}
	            	else
	            	{
	            		defs.put(aux.head, new HashSet<Instr>());
	            		defs.get(aux.head).add(inst);
	            	}
	            }
            }  
            
            gen.put(nodes.head, g);
        }

        // kill
        // use the defs to get the kill
        for(List<Node> nodes = graph.nodes(); nodes != null; nodes = nodes.tail)
        {
        	HashSet<Instr> k = new HashSet<Instr>();
        	inst = graph.instr(nodes.head);
        	
        	// verifica se ele define alguma coisa
        	if (inst.def() != null && inst.def().size() > 0)
            {
        		for ( List<Temp> aux = graph.def(nodes.head); aux != null; aux = aux.tail )
	            {
        			HashSet<Instr> l_instr = defs.get(aux.head);
        			// adiciona definicoes do temporario ao kill
        			// k = defs(t) - d
        			for (Instr inst_aux : l_instr)
        			{
        				if (! gen.get(nodes.head).contains(inst_aux))
        					k.add(inst_aux);
        			}
	            }
            }
        	
        	kill.put(nodes.head, k);
        }     
    }
    
    /* Compute the in and out of each node
     * in[n] = Up=pred[n] out[p]
     * out[n] = gen[n] U (in[n] - kill[n])
     */
    private void computeDFA()
    {	
    	in = new Hashtable<Node, HashSet<Instr>>();
    	out = new Hashtable<Node, HashSet<Instr>>();

    	/* Used to check if the set has been changed */
    	HashSet<Instr> in_prime = new HashSet<Instr>();
    	HashSet<Instr> out_prime = new HashSet<Instr>();
		
		/* Only need to do add the gen temps once */
    	/* out[n] = ***gen[n]*** U (in[n] - kill[n]) */
		for (List<Node> p = graph.nodes(); p != null; p = p.tail)
		{
			Node n = p.head;
			
			/* Create the empty hashsets */
			in.put(n, new HashSet<Instr>());
			out.put(n, new HashSet<Instr>());
			
			/* Add gen nodes */
			out.get(n).addAll(gen.get(n));
		}
		
		boolean stop;
    	
		/* Fixed point iteration */
    	do {
    		stop = true;
    		
    		for (List<Node> p = graph.nodes(); p != null; p = p.tail)
    		{
        		in_prime.clear();
        		out_prime.clear();
        		
    			Node n = p.head;
    			
    			in_prime.addAll(in.get(n));
    			out_prime.addAll(out.get(n));
    			
    			/* in[n] = Up=pred[n] out[p] */
    			/* Do for all predecessors */
    			for (List<Node> aux_pred = n.pred(); aux_pred != null; aux_pred = aux_pred.tail)
    			{
    				in.get(n).addAll(out.get(aux_pred.head));
    			}
    			
    			/* out[n] = gen[n] U ***(in[n] - kill[n])*** */
    			HashSet<Instr> aux_set = new HashSet<Instr>();
    			aux_set.addAll(in.get(n));
    			aux_set.removeAll(kill.get(n));
    			out.get(n).addAll(aux_set);
    			
    			/* If lists are equal than do not continue */
    			if ((! in_prime.containsAll(in.get(n))) || (! out_prime.containsAll(out.get(n))))
    				stop = false;
    		}
    	/* Verify if in and out have changed */
    	} while (! stop);
    }
    
    public HashSet<Instr> Defs(Temp node)
    {
        return defs.get(node);
    }

    public HashSet<Instr> In(Node node, Temp temp)
    {
    	HashSet<Instr> ret = new HashSet<Instr>();
    	
    	for (Instr inst : in.get(node))
    	{
    		for (List<Temp> aux = inst.def(); aux != null; aux = aux.tail)
    		{
    			if (aux.head == temp)
    			{
    				ret.add(inst);
    				continue;
    			}
    		}
    	}
    	
        return ret;
    } 

    public HashSet<Instr> Out(Node node)
    {
        return out.get(node);
    }
}
